Nonlinear dimensionality reduction (NLDR) generates a low-dimensional representation of high-dimensional sample data. The data are presumed to sample a d dimensional manifold  that is embedded in an ambient space D, with D>d. The goal is to separate the extrinsic geometry of the embedding, i.e., how the manifold  is shaped in the ambient space D, from its intrinsic geometry, i.e., the native d-dimensional coordinate system of the manifold .
For example, if it is known how a manifold of human faces is embedded in a space of image of the faces, the intrinsic geometric can be used to edit, compare, and classify images of faces, while the extrinsic geometry can be exploited to detect faces in images and synthesize new face images.
In computer vision it is common to approximate the manifold with linear subspaces fitted to sample images via principal components analysis (PCA). Although this is an approximation, it has been applied successfully for data interpolation, extrapolation, compression, denoising, and visualization.
NLDR “submanifold” methods can offer the same functionality, but with more fidelity to the true data distribution, because most of the operations are exclusive to the intrinsic or extrinsic geometry of the manifold .
Where PCA methods preserve a global structure of the manifold, i.e., a covariance about the data mean, NLDR methods preserve local structures in the manifold. Differential geometry teaches that local metrics on infinitesimal neighborhood of data and information about the connectivity of the neighborhoods fully determines the intrinsic geometry of the manifold.
This is approximated for finite data by imposing a neighborhood graph on the data and measuring relations between neighboring points in graph subsets.
The prior art describes imposing a neighborhood graph on the data and measuring relations between neighboring points in graph subsets for point-to-point distances, see, e.g., Tenenbaum, et al., “A global geometric framework for nonlinear dimensionality reduction,” Science, 290:2319-2323, December 2000, Weinberger, et al., “Learning a kernel matrix for nonlinear dimensionality reduction,” Proc. 21st ICML, 2004, and Belkin et al., “Laplacian eigenmaps for dimensionality reduction and data representation,” Advances in Neural Information Processing Systems, volume 14, 2002.
Measuring relations between neighboring points in graph subsets has also been described for coordinates of points projected into a local tangent space, see, Brand, “Charting a manifold,” Advances in Neural Information Processing Systems, volume 15, 2003, Donoho et al., “Hessian eigenmaps,” Proceedings, National Academy of Sciences, 2003, and Zhang et al., “Nonlinear dimension reduction via local tangent space alignment,” Proceedings, Conf. on Intelligent Data Engineering and Automated Learning, number 2690 in Lecture Notes on Computer Science, Springer-Verlag, pages 477-481, 2003.
Measuring relations between neighboring points in graph subsets has further been described for local barycentric coordinates, see, Roweis, et al., “Nonlinear dimensionality reduction by locally linear embedding,” Science, 290:2323-2326, December 2000.
A key assumption in prior art is that local linear structure of point subsets in the ambient space can approximate a metric structure in corresponding neighborhoods on the manifold , i.e., distances in ambient space D stand for geodesic arc-lengths on the manifold . The graph then guides the combination of all local metric constraints into a quadratic form where maximizing or minimizing eigenfunctions provide a minimum squared error basis for embedding the manifold in the target space d.
For discrete data, the quadratic form is a Gram matrix with entries that can be interpreted as inner products between points in an unknown space where the manifold is linearly embedded, therefore NLDR is a kernel method, albeit with unknown kernel function, see, Ham, et al., “A kernel view of the dimensionality reduction of manifolds,” Proc. ICML04, 2004.
Of particular interest for signal processing and data modeling is the case where a sampled patch in the manifold  is locally isometric to a connected patch of the target space d. Because in the continua limit of infinite sampling, optimizing eigenfunctions yields a flat immersion that perfectly reproduces the local data density and intrinsic geometry of the manifold, see, Donoho et al., “Hessian eigenmaps,” Proceedings, National Academy of Sciences, 2003. Thus, most NLDR embedding methods strive for isometry.
NLDR is derived from graph embeddings, see, e.g., Tutte, “Convex representations of graphs,” Proc. London Mathematical Society, 10:304-320, 1960, Tutte, “How to draw a graph,” Proc. London Mathematical Society, 13:743-768, 1963, Fiedler, “Algebraic connectivity of graphs,” Czechoslovak Mathematics Journal, 23:298-305, 1973, Fiedler, “Algebraic connectivity of graphs,” Czechoslovak Mathematics Journal, 23:298-305, 1973, and Chung, “Spectral graph theory,” CBMS Regional Conference Series in Mathematics, volume 92, American Mathematical Society, 1997.
Recent advance in machine learning are based on the insight that dimensionality reduction can be applied in the graph-embedding framework by estimating a graph and local metric constraints to cover datasets of unorganized points, see, Tenenbaum et al., Roweis et al., Brand, Belkin et al., and Donoho, et al., above. Applying NLDR in the graph-embedding framework presents two problems:    1. Local metric constraints are systematically distorted because data drawn from an extrinsically curved manifold are locally nonlinear at any finite scale. Therefore, distances in the ambient space D are biased approximations of geodesic arc-lengths on the manifold .    2. If the local estimated metric constraints contain any errors, the global solution has a minimum mean squared error (MMSE) with respect to a system of neighborhoods instead of an actual empirical data distribution.
Accordingly, the results of prior art NLDR methods are inconsistent and unstable, especially under small changes to the connectivity graph, see, Balasubramanian et al., “The IsoMap algorithm and topological stability,” Science, 295(5552):7, Jan. 2002.
Therefore, it is desired to provide a method for generating a low-dimensional representation of high-dimensional data that improves over the prior art.